import java.util.Scanner;

public class Homework {
    public static void main(String[] args) {
        /*
        已知有一个升序的数组，要求插入一个任意的元素，使得该数组依然是升序，比如：{10, 12, 45, 90} ,添加一个元素20后 ， 数组变为 {10, 12, 20, 45, 90}
        * */
//        Scanner myScanner = new Scanner(System.in);
//        int arr[] = {10, 12, 45, 90};
//        int newArr[] = new int[arr.length+1];
//        System.out.println("请输入你要插入的数:");
//        int num = myScanner.nextInt();
//        int temp = 0;
//        for (int i = 0; i < arr.length; i++) {
//            newArr[i] = arr[i];
//        }
//        newArr[arr.length] = num;
//        int min = newArr[arr.length];
//        for (int i = 0; i < newArr.length; i++) {
//            if(i>0 || min > newArr[newArr.length-1-i]){
//                temp = min;
//                min = newArr[newArr.length-1-i];
//                newArr[newArr.length-1-i] = temp;
//            }
//        }
//        arr = newArr;
//        for (int i = 0; i < arr.length; i++) {
//            System.out.print(arr[i] + "\t");
//        }

        /*思路分析：
        1. 这道题的本质是数组的扩容 + 定位
        2. 我们先确定被添加数应该插入到那个索引
            遍历数组，如果发现被插入的数小于便利的数，说明被插入的数的索引就是当前正在被遍历的数的索引，此时我们令 index = i;
            如果遍历完后，没有发现 insertNum <= arr[i], 说明 index = arr.length;
        3. 然后扩容
        * */
        //定位
        int arr[] = {10, 12, 45, 90};
        int insertNum = 20;
        int index = -1;//index 就是要插入的位置
        for (int i = 0; i < arr.length; i++) {
            if(insertNum <= arr[i]){
                index = i;
                break;//找到后退出
            }
        }
        //判断 index 的值
        if(index == -1){//说明还没有找到位置
            index = arr.length;
        }
        //扩容
        int newArr[] = new int[arr.length+1];
        for (int i = 0, j = 0; i < newArr.length; i++) {
            if(i != index){//说明可以把 arr 的元素拷贝到 newArr 中
                newArr[i] = arr[j];
                j++;
            }else {//i 这个位置就是要插入的数
                newArr[i] = insertNum;
            }

        }
        arr = newArr;
        System.out.println("插入后 arr 数组的情况：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "\t");
        }
    }
}
